#include<iostream>
const int capacity=10;
class MinHeap
{
public:
MinHeap():size(0){}
 void Insert(int value)
 {
    array[size]=value;
    SiftUp(size);
    size++;
 }

void show()
{
    for (int i = 0; i <size; i++)
    {
        std::cout<<array[i]<<" ";
    }
    std::cout<<std::endl;
}
void RemoveRoot()
{
    if (size==0)
    {
        return;
    }
    array[0]=array[--size];
    SiftDown(0);
}

private:
    int GetParent(int i){return (i-1)/2;}
    int GetLeftChild(int i){return 2*i+1;}
    int GetRightChild(int i){return 2*i+2;}
    void SiftUp(int i)
    {
        while (i>0&&array[i]<array[GetParent(i)])
        {
            std::swap(array[i],array[GetParent(i)]);
            i=GetParent(i);
        }
        
    }
    void SiftDown(int i)
    {
        int leftchild=GetLeftChild(i);
        int Rightchild=GetRightChild(i);

        int min =i;
        //右孩子存在比我左孩子的较大值大
        if(leftchild<size&&array[leftchild]<array[i])
        {
            min=leftchild;
        }
        if(Rightchild<size&&array[Rightchild]<array[min])
        {
            min=Rightchild;
        }
        if (min!=i)
        {
            std::swap(array[i],array[min]);
            SiftDown(min);
        }
        
    }

    int array[capacity];
    int size;//当前数组元素个数
};




int main()
{
 MinHeap h;
 for (int  i = 0; i < 10; i++)
 {
    h.Insert(i+1);
 }
 h.show();
 h.RemoveRoot();
 h.show();
 return 0;

}